#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:

    //剑指 Offer 52. 两个链表的第一个公共节点
    //法一：双指针
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if (headA==nullptr || headB==nullptr)
        {
            return nullptr;
        }
        ListNode* curA = headA;
        ListNode* curB = headB;
        while (curA != curB)
        {
            curA = curA==nullptr ? headB : curA->next;
            curB = curB==nullptr ? headA : curB->next;
        }
        return curA;
    }
    //法二：哈希表
    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
        if (headA==nullptr || headB==nullptr)
        {
            return nullptr;
        }
        unordered_set<ListNode*> st;
        ListNode* curA = headA;
        ListNode* curB = headB;
        while (curA)
        {
            st.insert(curA);
            curA = curA->next;
        }
        while (curB)
        {
            if (st.count(curB) > 0)
            {
                return curB;
            }
            curB = curB->next;
        }
        return nullptr;
    }

    //剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
    vector<int> exchange(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while (left < right)
        {
            //找偶数
            while (left < right && nums[left] % 2 != 0)
            {
                ++left;
            }
            //找奇数
            while (left < right && nums[right] % 2 != 1)
            {
                --right;
            }
            if (left < right)
            {
                swap(nums[left], nums[right]);
            }
        }
        return nums;
    }
};